package top.ivansong92.example.leetcode.learning.common.algorithms.dynamic;


import org.junit.Test;

import java.util.*;

public class TestExample {
    /**
     * 合并两个有序数组
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/8/sorting-and-searching/52/
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = 0, j = 0, k = 0;
        int[] res = new int[nums1.length];
        while (j < n || i < m) {
            if (j >= n) {
                res[k++] = nums1[i++];
                continue;
            }
            if (i >= m) {
                res[k++] = nums2[j++];
                continue;
            }
            if (nums1[i] < nums2[j]) {
                res[k++] = nums1[i++];
            } else {
                res[k++] = nums2[j++];
            }
        }

        k = 0;
        for (; k < res.length; k++) {
            nums1[k] = res[k];
        }
    }

    @Test
    public void test1() {
        merge(new int[]{1, 0}, 1, new int[]{2}, 1);
    }

    /**
     * 70. 爬楼梯
     * https://leetcode-cn.com/problems/climbing-stairs/
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int[] a = new int[n];
        a[0] = 1;
        a[1] = 2;
        for (int i = 2; i < n; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }
        return a[n - 1];
    }



    @Test
    public void testMinimumTotal() {
        System.out.println(minimumTotalV2(Arrays.asList(Arrays.asList(2) , Arrays.asList(3,4), Arrays.asList(6,5,7),Arrays.asList(4,1,8,3))));
    }

    /**
     * 120. 三角形最小路径和
     */
    public int minimumTotalV2(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }

        int n = triangle.size();
        if (n == 1) {
            return triangle.get(0).get(0);
        }

        int[][] triangleArray = new int[n][n];
        List<Integer> last = triangle.get(n - 1);
        for (int j = 0; j < last.size(); j++) {
            triangleArray[n - 1][j] = last.get(j);
        }

        for (int i = n - 2; i >= 0; i--) {
            List<Integer> current = triangle.get(i);
            for (int j = 0; j < current.size(); j++) {
                triangleArray[i][j] = current.get(j) + Math.min(triangleArray[i + 1][j], triangleArray[i + 1][j + 1]);
            }
        }

        return triangleArray[0][0];
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }

        if (triangle.size() == 1) {
            return triangle.get(0).stream().mapToInt(Integer::intValue).min().orElse(0);
        }

        List<Integer> traceList = new ArrayList<>();
        dfsNumTree(0, 0, 0, traceList, triangle, triangle.size());
        return traceList.stream().mapToInt(Integer::intValue).min().orElse(0);
    }

    private void dfsNumTree(int parentVal, int height, int index, List<Integer> traceList, List<List<Integer>> triangle, int maxHeight) {
        if (height == maxHeight) {
            traceList.add(parentVal);
            return;
        }

        int nextHeight = height + 1;
        int val1 = triangle.get(height).get(index) + parentVal;

        dfsNumTree(val1, nextHeight, index, traceList, triangle, maxHeight);
        dfsNumTree(val1, nextHeight, index + 1, traceList, triangle, maxHeight);
    }



    /**
     * 64. 最小路径和
     * @param grid
     * @return
     */

    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        if (m == 1) {
            int res = 0;
            for (int val : grid[0]) {
                res += val;
            }
            return res;
        } else if (n == 1) {
            int res = 0;
            for (int[] ints : grid) {
                res += ints[0];
            }
            return res;
        }

        int[][] stepArray = new int[m][n];
        stepArray[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            stepArray[i][0] = grid[i][0] + stepArray[i - 1][0];
        }

        for (int j = 1; j < n; j++) {
            stepArray[0][j] = grid[0][j] + stepArray[0][j - 1];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                stepArray[i][j] = grid[i][j] + Math.min(stepArray[i][j - 1], stepArray[i - 1][j]);
            }
        }

        return stepArray[m - 1][n - 1];
    }

    @Test
    public void testintegerBreak() {
        System.out.println(integerBreak(10));
    }


    /**
     * 343. 整数拆分
     * @param n
     * @return
     */
    public int integerBreak(int n) {
        int[] tmp = new int[n + 1];
        return doBreakCal(n, tmp);
    }

    private int doBreakCal(int max, int[] array) {
        if (max <= 2) {
            return 1;
        }

        if (array[max] != 0) {
            return array[max];
        }

        int res = -1;

        for (int i = 1; i <= max - 1; i++) {
            res = Math.max(Math.max(res, i * (max - i)), i * doBreakCal(max - i, array));
        }
        array[max] = res;
        return res;
    }

    /**
     * 91. 解码方法
     * @param s
     * @return
     */

    public int numDecodingsV2(String s) {
        if (s == null || s.length() == 0 || s.startsWith("0")) {
            return 0;
        }

        int len = s.length();
        if (len == 1) {
            return 1;
        }

        int[] tmpArray = new int[len + 1];
        tmpArray[0] = 1;
        String sub = s.substring(0, 2);
        int val = Integer.parseInt(sub);
        int mod = val % 10;
        if (val > 26 || mod == 0) {
            tmpArray[1] = 1;
        } else {
            tmpArray[1] = 2;
        }

        for (int i = 2; i < len; i++) {
            char ch = s.charAt(i);
            if (ch == '0') {
                tmpArray[i] = tmpArray[i - 2];
                continue;
            }
            char last = s.charAt(i - 1);

        }
        return tmpArray[len];
    }


    @Test
    public void testnumDecodings1() {
        System.out.println(numDecodings1("226"));
    }
    public int numDecodings1(String s) {
        if (s == null || s.length() == 0 || s.startsWith("0")) {
            return 0;
        }

        int len = s.length();
        if (len == 1) {
            return 1;
        }
        Map<String, Integer> map = new HashMap<>();
        int rs = doGetDeNum(s, map);
        return rs;
    }
    private int doGetDeNum(String s, Map<String, Integer> map) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }

        Integer val = map.get(s);
        if (val != null) {
            return val;
        }

        int res;
        if (len > 2) {
            String subStr = s.substring(0,2);
            if (!subStr.startsWith("0")) {
                int sVal = parseInt(subStr);
                if (sVal > 26) {
                    if (sVal % 10 == 0) {
                        res = 0;
                    } else {
                        res = doGetDeNum(s.substring(1), map);
                    }
                } else {
                    if (sVal % 10 == 0) {
                        res = doGetDeNum(s.substring(2), map);
                    } else {
                        res = doGetDeNum(s.substring(2), map) + doGetDeNum(s.substring(1), map);
                    }
                }
            } else {
                res = 0;
            }
        } else if (s.startsWith("0")) {
            res = 0;
        } else if (len == 2) {
            int sVal = parseInt(s);
            if (sVal > 26) {
                if (sVal % 10 == 0) {
                    res = 0;
                } else {
                    res = 1;
                }
            } else {
                if (sVal % 10 == 0) {
                    res = 1;
                } else {
                    res = 2;
                }
            }
        } else {
            res = 1;
        }
        map.put(s, res);
        return res;
    }

    private int parseInt(String s) {
        int val = 0;
        for (char ch : s.toCharArray()) {
            val = val * 10 + (ch - '0');
        }
        return val;
    }


    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.startsWith("0")) {
            return 0;
        }

        int len = s.length();
        if (len == 1) {
            return 1;
        }
        List<String> lefList = new ArrayList<>();
        doFindDecodingLef(s, lefList);
        return lefList.size();
    }

    private void doFindDecodingLef(String s, List<String> list) {
        if (s == null || s.length() == 0 || s.startsWith("0")) {
            return;
        }
        int len = s.length();
        if (len > 2) {
            String subStr = s.substring(0, 2);
            int val = Integer.parseInt(subStr);
            int mod = val % 10;
            if (mod == 0) {
                if (val < 30) {
                    doFindDecodingLef(s.substring(2, len), list);
                }
                return;
            }

            if (val <= 26) {
                doFindDecodingLef(s.substring(2, len), list);
            }
            doFindDecodingLef(s.substring(1, len), list);
        } else if (len == 2) {
            int val = Integer.parseInt(s);
            int mod = val % 10;
            if (mod == 0 && val > 20) {
                return;
            }

            if (mod == 0) {
                list.add(s);
                return;
            }

            if (val <= 26) {
                list.add(s);
            }
            doFindDecodingLef(s.substring(0, 1), list);
            doFindDecodingLef(s.substring(1, 2), list);
        } else {
            list.add(s);
        }

    }

    /**
     * 53. 最大子序和
     * https://leetcode-cn.com/problems/maximum-subarray/
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int [] temp = new int[nums.length];
        int max = nums[0];
        temp[0] = max;
        for(int i = 1; i < nums.length; i ++) {
            int val = nums[i];
            int add_val = nums[i] + temp[i - 1];
            if (add_val > val) {
                temp[i] = add_val;
            } else {
                temp[i] = val;
            }
            max = Math.max(max, temp[i]);
        }
        return max;
    }

    /**
     * 121. 买卖股票的最佳时机
     * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int max = 0;
        int[] temp = new int[prices.length];
        temp[0] = 0;
        for(int i = 1; i < prices.length; i ++) {
            int val = prices[i] - prices[i - 1] + temp[i - 1];
            if (val > 0) {
                temp[i] = val;
                max = Math.max(val, max);
            } else {
                temp[i] = 0;
            }
        }
        return max;
    }


    /**
     * 198. 打家劫舍
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/23/dynamic-programming/57/
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        if (nums.length == 1) {
            return nums[0];
        }

        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        int [] temp = new int[nums.length];
        temp[0] = nums[0];
        int max = Math.max(nums[0], nums[1]);
        temp[1] = max;
        for(int i = 2; i < nums.length; i ++) {
            int val = nums[i] + temp[i - 2];
            max = Math.max(val, max);
            temp[i] = max;
        }
        return max;
    }

    public int robV3(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }

        if (len == 2) {
            return Math.max(nums[0], nums[1]);
        }

        int max = Math.max(nums[0], nums[1]);
        int last = nums[0];
        for(int i = 2; i < nums.length; i ++) {
            int val = nums[i] + last;
            last = max;
            max = Math.max(val, max);
        }
        return max;
    }


    @Test
    public void test2() {
        System.out.println(robV3(new int[]{2,1,3,4}));
    }


}